package java_zuoye_2;

import java.util.Arrays;

public class homework_10 {
	public static void shellSort(int[] array) {
        int n = array.length;
        int gap = n / 2;  // 初始间隔为数组长度的一半
        while (gap > 0) {
            // 通过插入排序对每个间隔进行排序
            for (int i = gap; i < n; i++) {
                int temp = array[i];
                int j = i;
                
                // 对间隔为 gap 的子数组进行插入排序
                while (j >= gap && array[j - gap] > temp) {
                    array[j] = array[j - gap];
                    j -= gap;
                }
                array[j] = temp;
            }
            gap /= 2;  // 缩小间隔
        }
    }
    public static void main(String[] args) {
        int[] array = {5, 2, 8, 1, 3};
        
        System.out.println("开始的 array: " + Arrays.toString(array));
        
        shellSort(array);
        
        System.out.println("排序好的 array: " + Arrays.toString(array));
    }
}


/*
在算法开始时，将间隔（gap）初始化为数组长度的一半。
通过逐个比较并交换元素的方式，对每个间隔位置上的子数组进行插入排序。
当完成当前间隔的排序后，将间隔缩小为原来的一半。
重复以上两步，直到间隔缩小到1，此时使用插入排序对整个数组进行最后的排序。

希尔排序的关键在于通过较大的间隔在子数组中移动元素，从而可以更快地将大的元素移动到正确的位置。
随着排序的进行，间隔逐渐缩小，直到最后一次使用间隔为1的插入排序。
*/